class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

class Solution1 {
    public int massage(int[] nums) {
        int n=nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int[] dp1=new int[n];
        int[] dp2=new int[n];

        dp1[0]=nums[0];
        dp1[1]=nums[1];

        dp2[0]=0;
        dp2[1]=nums[0];


        for(int i=2;i<n;i++){
            dp1[i]=dp2[i-1]+nums[i];
            dp2[i]=Math.max(dp1[i-1],dp1[i-2]);
        }

        return Math.max(dp1[n-1],dp2[n-1]);



    }
}


class Solution2 {
    public int rob(int[] nums) {
        int n=nums.length;

        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);


        if(n<3) return 0;
        if(n==3) return Math.max(nums[2],Math.max(nums[0],nums[1]));

        int ret=rob(2,n-1,nums)+nums[0];

        ret=Math.max(ret,rob(1,n,nums));


        return ret;


    }

    private int rob(int start,int end,int[] nums){
        int n=nums.length;


        int[] dp1=new int[n];
        int[] dp2=new int[n];

        dp1[start]=nums[start];
        dp1[start+1]=nums[start+1];

        dp2[start]=0;
        dp2[start+1]=nums[start];


        for(int i=start+2;i<end;i++){
            dp1[i]=dp2[i-1]+nums[i];
            dp2[i]=Math.max(dp1[i-1],dp1[i-2]);
        }

        return Math.max(dp1[end-1],dp2[end-1]);

    }
}


class Solution3 {
    public int deleteAndEarn(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        int n=10001;

        int[] arr=new int[n];
        for(int x:nums) arr[x]+=x;

        int[] dp1=new int[n];
        int[] dp2=new int[n];

        dp1[0]=arr[0];
        dp1[1]=Math.max(arr[0],arr[1]);

        dp2[1]=arr[0];

        for(int i=2;i<n;i++){
            dp1[i]=arr[i]+dp2[i-1];
            dp2[i]=Math.max(dp1[i-1],dp1[i-2]);

        }
        return Math.max(dp1[n-1],dp2[n-1]);
    }
}



class Solution4 {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 0) return 0;

        // 找到数组中的最大值，用于确定数组的大小
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        // 统计每个数字的总和
        int[] sum = new int[maxVal + 1];
        for (int num : nums) {
            sum[num] += num;
        }

        // 使用滚动数组优化空间复杂度
        int pick = 0; // 当前选择当前数字时的最大收益
        int notPick = 0; // 当前不选择当前数字时的最大收益

        for (int i = 1; i <= maxVal; i++) {
            int newPick = sum[i] + notPick; // 如果选择当前数字，则不能选择前一个数字
            int newNotPick = Math.max(pick, notPick); // 如果不选择当前数字，则取前一个状态的最大值

            pick = newPick;
            notPick = newNotPick;
        }

        // 返回两种情况的最大值
        return Math.max(pick, notPick);
    }
}